package Lee_code;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Lee_15 {
    public List<List<Integer>> threeSum(int[] nums) {

        int len = nums.length;
        List<List<Integer>> result = new LinkedList<>();
        Arrays.sort(nums);

        for(int i=0; i<len-2; i++)
        {
            if(i>0&&nums[i]==nums[i-1])
            {
                continue;
            }
            for(int left=i+1; left<len-1; left++)
            {
                if(left>(i+1)&&nums[left]==nums[left-1])
                {
                    continue;
                }
                int right = len-1;
                int target = -nums[i];
                while(right>left)
                {
                    if((nums[left] + nums[right])>target )
                        right--;
                    else if ((nums[left] + nums[right])<target)
                        left++;
                    else if ((nums[left] + nums[right])==target)
                    {
                        List<Integer> temp = new LinkedList<>();
                        temp.add(i);
                        temp.add(left);
                        temp.add(right);
                        result.add(temp);
                    }
                }
            }
        }
        return result;
    }
    public static void main(String[] args) {

    }
}
